package strategy

import (
	"container/heap"
	"errors"
	"math"
)

type Item struct {
	value    string
	priority float64
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority < pq[j].priority }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i]; pq[i].index = i; pq[j].index = j }

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

func buildPath(graph *Graph, source, destination string, prev map[string]string) *Path {
	path := &Path{
		Source:      source,
		Destination: destination,
		Links:       []*LinkWithAttrs{},
		TotalCost:   0,
		TotalDelay:  0,
		AvailableBW: math.MaxFloat64,
	}

	current := destination
	for current != source {
		prevNode := prev[current]
		link := graph.Nodes[prevNode].Adjacents[current]

		if link == nil {
			break
		}

		path.Links = append([]*LinkWithAttrs{link}, path.Links...)
		path.TotalCost += float64(link.Metric)
		path.TotalDelay += link.Delay
		if link.Bandwidth < path.AvailableBW {
			path.AvailableBW = link.Bandwidth
		}

		current = prevNode
	}

	return path
}

func multiObjectiveDijkstra(
	graph *Graph,
	source, destination string,
	scoreFunc func(*LinkWithAttrs, MultiObjectiveScore) MultiObjectiveScore,
	initialScore MultiObjectiveScore,
) (*Path, error) {

	bestScores := make(map[string]MultiObjectiveScore)
	prev := make(map[string]string)

	bestScores[source] = initialScore

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, &Item{value: source, priority: initialScore[0]})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(*Item).value

		if current == destination {
			break
		}

		node := graph.Nodes[current]
		if node == nil {
			continue
		}

		for neighborID, link := range node.Adjacents {
			neighbor := graph.Nodes[neighborID]
			if neighbor == nil {
				continue
			}

			currentScore := bestScores[current]
			newScore := scoreFunc(link, currentScore)

			existingScore, exists := bestScores[neighborID]
			if !exists || newScore.Compare(existingScore) < 0 {
				bestScores[neighborID] = newScore
				prev[neighborID] = current
				heap.Push(pq, &Item{value: neighborID, priority: newScore[0]})
			}
		}
	}

	if _, ok := prev[destination]; !ok {
		return nil, errors.New("未找到路径")
	}

	return buildPath(graph, source, destination, prev), nil
}

func multiObjectiveDijkstraWithVisitLog(
	graph *Graph,
	source, destination string,
	scoreFunc func(*LinkWithAttrs, MultiObjectiveScore) MultiObjectiveScore,
	initialScore MultiObjectiveScore,
) (*Path, map[string]bool, error) {

	bestScores := make(map[string]MultiObjectiveScore)
	prev := make(map[string]string)
	visited := make(map[string]bool)

	bestScores[source] = initialScore

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, &Item{value: source, priority: initialScore[0]})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(*Item).value
		visited[current] = true

		if current == destination {
			break
		}

		node := graph.Nodes[current]
		if node == nil {
			continue
		}

		for neighborID, link := range node.Adjacents {
			neighbor := graph.Nodes[neighborID]
			if neighbor == nil {
				continue
			}

			currentScore := bestScores[current]
			newScore := scoreFunc(link, currentScore)

			existingScore, exists := bestScores[neighborID]
			if !exists || newScore.Compare(existingScore) < 0 {
				bestScores[neighborID] = newScore
				prev[neighborID] = current
				heap.Push(pq, &Item{value: neighborID, priority: newScore[0]})
			}
		}
	}

	if _, ok := prev[destination]; !ok {
		return nil, nil, errors.New("未找到路径")
	}

	path := buildPath(graph, source, destination, prev)
	return path, visited, nil
}

// MultiObjectiveScore 多维评分
type MultiObjectiveScore []float64

func (s MultiObjectiveScore) Compare(other MultiObjectiveScore) int {
	for i := range s {
		if i >= len(other) {
			return 1
		}
		if s[i] < other[i] {
			return -1
		} else if s[i] > other[i] {
			return 1
		}
	}
	return 0
}
